#include <cstdio>
#include <cstring>

struct Matrix
{
    int a[ 31 ][ 31 ];
    Matrix( )
    {
        int i, j;
        for ( i = 0; i < 31; i++ )
            for ( j = 0; j < 31; j++ )
                a[ i ][ j ] = 0;
    }
};

Matrix operator * ( const Matrix &a, const Matrix &b )
{
    Matrix c;
    int i, j, k;
    for ( i = 0; i < 31; i++ )
        for ( j = 0; j < 31; j++ )
            for ( k = 0; k < 31; k++ )
                c.a[ i ][ j ] = ( c.a[ i ][ j ] + a.a[ i ][ k ] * b.a[ k ][ j ] ) % 10001;
    return c;
}

Matrix f, mat, mat_back;
int n, m, en;
char s[ 31 ][ 11 ], start[ 31 ], end[ 31 ];

void init( )
{
    int i, j;
    scanf("%d", &m);
    for ( i = 0; i < m; i++ )
        scanf("%s", s[ i ]);
    scanf("%s%s%d", start, end, &n);
    for ( i = 0; i <= m; i++ )
        for ( j = 0; j <= m; j++ )
            f.a[ i ][ j ] = mat.a[ i ][ j ] = mat_back.a[ i ][ j ] = 0;
        for ( i = 0; i < m; i++ )
        {
            if ( strcmp( start, s[ i ] ) == 0 )
                f.a[ 0 ][ i ] = 1;
            for ( j = 0; j < m; j++ )
                if ( s[ i ][ strlen( s[ i ] ) - 1 ] == s[ j ][ 0 ] )
                    mat_back.a[ i ][ j ] = 1;
        }
        f = f * mat_back;
        mat_back = mat_back * mat_back;
    for ( i = 0; i < m; i++ )
    {
        if ( strcmp( end, s[ i ] ) == 0 )
        {
            en = i;
            mat_back.a[ i ][ m ] = 1;
            mat_back.a[ m ][ m ] = 1;
        }
        mat.a[ i ][ i ] = 1;
    }
    mat.a[ m ][ m ] = 1;
}

void work( )
{
    int pos = 1, i, j;
    if ( n <= 0 )
    {
        printf("0\n");
        return ;
    }
    n = ( n - 1 ) / 2;
    while ( pos < n )
        pos <<= 1;
    while ( pos )
    {
        mat = mat * mat;
        if ( pos & n )
            mat = mat * mat_back;
        pos >>= 1;
    }
    f = f * mat;
    printf("%d\n", ( f.a[ 0 ][ en ] + f.a[ 0 ][ m ] ) % 10001);
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
    }
    return 0;
}
